package DS2;
//初阶数据结构：顺序表 链表 栈 队列 二叉树 排序 优先级队列 哈希表 二叉搜索树
//高阶数据结构：AVL树 红黑树 B树 B+树 图(7种算法) 查找-》位图 布隆过滤器 LRU算法
//算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作
//空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，

//时间复杂度：
//时间复杂度的计算不光要看代码的执行，还要结合某些算法的思想来计算
public class Test1 {
    void func1(int N) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count++;
            }
        }
        for (int k = 0; k < 2 * N; k++) {
            count++;
        }
        int M = 10;
        while ((M--) > 0) {
            count++;
        }
        System.out.println(count);
    }
    //这个代码执行了F(N)=N^2+2*N=10次数
    //外层循环了1次，内层循环了N次，所以是N*N，第二个循环是2*N，最后一个是10次

    //实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们
    //使用大O的渐进表示法。

    推导大O阶方法
    1、用常数1取代运行时间中的所有加法常数。
    2、在修改后的运行次数函数中，只保留最高阶项。
    3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。


    //那么这个func1的时间复杂度是O(M^2)

    void func2(int N) {
        int count = 0;
        for (int k = 0; k < 2 * N; k++) {
            count++;
        }
        int M = 10;
        while ((M--) > 0) {
            count++;
        }
        System.out.println(count);
    }
    //执行的次数是：2*N+10
    //所以大O表示法：O(N);

    void func3(int N, int M) {
        int count = 0;
        for (int k = 0; k < M; k++) {
            count++;
        }
        for (int k = 0; k < N; k++) {
            count++;
        }
        System.out.println(count);
    }
    //执行的次数是：M+N
    //所以大O表示法：O(M+N);

    void func4(int N) {
        int count = 0;
        for (int k = 0; k < 100; k++) {
            count++;
        }
        System.out.println(count);
    }
    //执行的次数是：100
    //所以大O表示法：O(1)

    void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i - 1] > array[i]) {

                    Swap(array, i - 1, i);
                    sorted = false;
                }
            }
            if (sorted == true) {
                break;
            }
        }
    }
    // 最好：O(N) 执行了N次
    // 最坏：O(N^2) 执行了N*(N-1)/2次

    int binarySearch(int[] array, int value) {
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end) {
            int mid = begin + ((end - begin) / 2);
            if (array[mid] < value)
                begin = mid + 1;
            else if (array[mid] > value)
                end = mid - 1;
            else
                return mid;
        }
        return -1;
    }
    //最好执行了1次
    //因为每次二分查找就是把一半的值去除掉，
    //设原来的数组有N个元素，每次去折半，所以都是不短的去除一半，一直到仅剩1的时候
    //N/2，N/4，N/8.N/16
    //N/2^x 所以转换为就是lgN
    //所以时间复杂度为O(lgN)

    long factorial(int N) {
        return N < 2 ? N : factorial(N - 1) * N;
    }
    //递归的时间复杂度
    //每次都是不断地往下去递推，但是每次的递推就是执行了一次，计算了一次的乘积，所以就相当于递归了N次
    //所以时间复杂度O(N).

    int fibonacci(int N) {
        return N < 2 ? N : fibonacci(N - 1) + fibonacci(N - 2);
    }
    //                                      f(n)                                                    1
    //                  f(n-1)                                      f(n-2)                          2
    //          f(n-2)           f(n-3)                      f(n-3)           f(n-4)                4
    //      f(n-3)  f(n-4)    f(n-4)  f(n-5)             f(n-4)  f(n-5)   f(n-5)  f(n-6)            8

    //所以我们根据这个规律可以发现 最后会执行了n次，
    //我们会发现了这是一个等比数列，公比为2
    //2^0 + 2^1 + 2^2 + 2^3 + ………… +2^(n-1)
    //所以我们可得求和为(2^n)-1约等于2^n
    //所以这个是时间复杂度为O(2^n)


    //常见的时间复杂度：O(1) < O(lgN) < O(N) < O(N*logN) < O(N^2)
    public static void main(String[] args) {
        System.out.println("Hello");
    }
}
